Cyclic Redundancy Check (CRC) is a term used to describe a family or range of error-checking codes that are used in data communication systems. CRC is based on finite field polynomial arithmetic. Some common Cyclic Redundancy Check standards are CRC-8, CRC-12, CRC-16, CRC-32, and CRC-CCIT.
CRC can be performed in serial or parallel modes. In parallel mode, the width of input data to a parallel CRC module is determined by a width, k, of the data bus. A generator polynomial function is used to compute the CRC output from two inputs. Typically, these two inputs are an input data word, data-in, and an initial value, init. The choice of generator polynomial can be varied according to desired performance and environment. It is known in the art that certain polynomials are more effective than others. At the start of the entire CRC process, the initial value is given as start value, but in subsequent CRC calculations it assumes a value derived from a previous CRC calculation.
There are at least two possible general CRC procedures that might be applied when preparing to transmit data. The first possible procedure passes all original data to be transmitted through the CRC module to generate a final output CRC value of data width m. The output CRC value is appended to the end of the original input data and the entire contents, that is, original data and output CRC value, are transmitted to a receiver. The receiver splits the received data into received input data words and received output CRC value. The receiver has a CRC module that performs the same CRC calculations on the received input data. If the received input data has been transmitted without any errors, then the CRC value, of data width m, calculated by the receiving CRC module will match the CRC value that was appended to the end of the original data. The absence of such a match provides a basis for performing error detection and correction.
A second possible CRC procedure appends a number, m, of zero bits to the end of the original data to be transmitted to produce extended data. The number, m, is governed by the number of bits of the CRC output value. This extended data is passed through the CRC module to produce an m bit CRC output value. The CRC output value replaces the appended m zero bits at the end of the data which produces revised extended data. The revised extended data is transmitted to a receiver. The entire length of the received data is fed into the CRC module of the receiver. The receiver CRC module performs the same CRC calculations using all of the received data. The receiving CRC module will give an output CRC value of zero if the transmission has been error free.
FIG. 1 shows schematically a CRC device or method 100 comprising a basic parallel CRC module 105, having an m-bit wide CRC initialisation value input 110, a k-bit wide data input 115, and an m-bit wide CRC output 120. An overall CRC calculation, for a data stream comprising more than k bits, is produced by dividing the data stream into a number of k-bit wide input data words and calculating a partial CRC result for a given input data word presented at the k-bit wide data input 115 and passing the partial CRC back to be used as the initial CRC value for the next partial CRC calculation using the next k-bit wide input word of the data stream. For example, the CRC module might use a 32-bit initial value and 128 bits of input data (k bits of data) to produce a 32-bit CRC output value 120. The transmitted packet would comprise a number of data bits followed by a number of CRC bits in the form of a Frame Check Sequence, FCS.
It can be appreciated that if the data stream does not contain an integer multiple of k-bit words, the final few bits of that data stream will not represent a complete data word suitable for processing by the parallel CRC module.
The accurate calculation of the final partial CRC on this final data word is required to support error free transmission of data. A problem can thus occur when the last data word is incomplete, that is, the number of valid data bits, n, of the data stream is less than the k bits of the data word used by the CRC module.
There are two general methods in the prior art for using parallel CRC's to accommodate such a final word having less than an anticipated number of bits. These two methods will be explained below with reference to FIGS. 2 and 3 respectively. Both are given as specific examples using k=128 bit data words and m=32 bit CRC modules to produce 32-bit CRC outputs. Both methods are given with an assumption that the data is transmitted most significant bit, msb, first. Thus, the data [127:120] is the first byte of data of a 128-bit data word or data stream. The last word of data in each solution is accompanied by a mod 230 signal which signifies how many of the data bits in the last data word are valid.
FIG. 2 shows a first parallel CRC system 200. It uses a number of CRC modules 205, 210, 215, 220 of different, incrementing, data widths to calculate the possible CRC results for a given data word. The results are fed into a multiplexer 225 along with a mod signal 230 that provides information on the number of valid data bits in the final word. The mod signal 230 allows the multiplexer 225 to select the appropriate output of the CRCs 205 to 220. As mentioned above, the mod signal 230 provides and indication of the number of valid data bits in a current word for which a CRC value is being calculated. For example, processing a data stream of 136 bits would use the 128-bit CRC module 220 to produce a first or partial CRC output and the 8-bit CRC module to produce a second CRC output. The first and second partial results are used to calculate the overall CRC output 235 for the 136-bit data stream. This approach is a fast method of accommodating variable length data streams. However, the design is large and, hence, area and power inefficient when implemented in silicon, that is, in hardware.
FIG. 3 shows a second parallel CRC system 300. It is based on an incremental process. A number, m, of 8-bit CRC modules 305, 310, 315, 320 are arranged in series such that each CRC passes a partial CRC result 325a, 325b, 325c to the next CRC in the sequence until the final, or maximum, CRC result 330 is calculated. Assuming that a 128-bit data word is to be processed, the first CRC module 305 takes the first 8 bits 335 of the data word, performs the CRC calculation, then feeds the partial CRC result 325a obtained to the next CRC module 310. The next CRC module 310 uses the partial CRC result 325a together with the next 8 bits 340 of the 128-bit data stream to produce a second partial CRC result 325b and so on until the final 8 bits 350 of the data stream are processed by the final CRC module 320 to produce a final or overall CRC result 330. The partial CRC results 325a, 325b, 325c and final CRC result 330 are fed into, or selected by, a multiplexer 225 that uses a mod signal 230 to select the correct CRC partial or final result to produce an appropriate CRC output 235 according to the length of the input data word being processed. It will be appreciated that variable length data can be accommodated using this design, providing the data length is an integer multiple of the number of bits processed by CRCs 305 to 320. This approach uses less area than the first but is slower because of the serial nature by which the CRC partial results are passed along the chain of CRC modules. Also, a further disadvantage is that the data width of each cascaded CRC module has to be chosen so as to anticipate or accommodate the number of valid data bits, n.
Prior art CRC calculations have been performed using either or a combination of the above two solutions. They use CRC calculations over a range of data widths and have a multiplexer with a mod signal to determine which CRC result is the correct one for the number of valid data bits within a given word. Multiple calculations are required and many CRC modules are required, along with a multiplexer, for performing and selecting the appropriate CRC result. It is apparent from the foregoing that the determination of the CRC output for variable length data or the last data word of a data stream is inefficient in terms of both area, time and power consumption and the number of valid bits in the last word has to be designed into the circuit and is generally inflexible.
It is an object of embodiments of the present invention, at least, to mitigate some of the problems of the prior art.